/*
Date:20210427 17:29PM
key:一定是先买入再卖出，所以用一个数组存截至到i的最小值min[i],然后每个prices[i]-min[i].其中最大的返回。
*/
class Solution {
public:
    int maxProfit(vector<int>& prices) 
    {
        if(prices.size()==1){return 0;}
        int*min=new int[prices.size()];
        for(int i=0;i<prices.size();i++)
        {
            if(i==0)
            {
                min[i]=prices[0];
            }
            else
            {
                if(prices[i]<min[i-1])
                {
                    min[i]=prices[i];
                }
                else
                {
                    min[i]=min[i-1];
                }
            }
        }
        for(int i=0;i<prices.size();i++)
        {
            prices[i]-=min[i];
        }
        int max=0;
                for(int i=0;i<prices.size();i++)
        {
            if(max<prices[i])
            {
                max=prices[i];
            }
            
        }
        return max;
    }
};